import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 1043. 分割数组以得到最大和
 * 给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
 * <p>
 * 返回将数组分隔变换后能够得到的元素最大和。
 * <p>
 * 注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。
 */
public class MaxSumAfterPartitioning {


    @Test
    public void test1() {
        Assertions.assertEquals(84, maxSumAfterPartitioning(new int[]{1, 15, 7, 9, 2, 5, 10}, 3));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(83, maxSumAfterPartitioning(new int[]{1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3}, 4));
    }

    @Test
    public void test3() {
        Assertions.assertEquals(1, maxSumAfterPartitioning(new int[]{1}, 1));
    }


    public int maxSumAfterPartitioning(int[] arr, int k) {
        if (k == 0) {
            return 0;
        }
        /*
         * 第i个值代表：
         * 不包含arr[i]，从 arr[0] 到 arr[i-1]所组成的最大和
         * 根据定义，那么 arr[i]的结果就存储在 cache[i+1] 上
         * 所以cache的长度要+1
         * */
        int[] cache = new int[arr.length + 1];

//      第0个的最大和 因为不能包含 arr[0]，所以无论如何都是0
        cache[0] = 0;

//        遍历 cache
        for (int i = 1, max = 0; i < cache.length; i++) {
/*          当遍历到第 cache[i]时，它的结果为以下情况其中的一个最大值：
            cache[i-1]+arr[i-1]*1       前 cache[i-1]的和 + arr[i-1] 占 1 位长度

            cache[i-2]+arr[i-2]*2       前 cache[i-2]的和 + arr[i-2] 占 2 位长度
            cache[i-2]+arr[i-1]*2       前 cache[i-2]的和 + arr[i-1] 占 2 位长度

            cache[i-3]+arr[i-3]*3       前 cache[i-3]的和 + arr[i-3] 占 3 位长度
            cache[i-3]+arr[i-2]*3       前 cache[i-3]的和 + arr[i-2] 占 3 位长度
            cache[i-3]+arr[i-1]*3       前 cache[i-3]的和 + arr[i-1] 占 3 位长度

            以此类推...

            如此实现下来，就是下面的两个for循环
 */
            for (int j = i - 1, ki = 1; j >= Math.max(i - k, 0); j--, ki++) {

                for (int l = 0; l < ki; l++) {
                    max = Math.max(max, cache[j] + arr[j + l] * ki);
                }
            }
            cache[i] = max;
            max = 0;
        }


        return cache[cache.length - 1];
    }
}
